package LeetCode;

public class LC_684_RedundantConnection {

    public static void main(String[] args) {

    }

    class Solution {
        public int[] findRedundantConnection(int[][] edges) {
            int[] a = new int[2000 + 1];
            int cnt = 1;
            for (int[] edge : edges) {
                int i = edge[0], j = edge[1];
                if (a[i] == 0 && a[j] == 0) {
                    a[i] = cnt;
                    a[j] = cnt;
                    cnt++;
                } else if (a[i] != 0 && a[j] != 0) {
                    if (a[i] == a[j]) return edge;
                    else {
                        int tmp = a[j];
                        for (int k = 0; k < a.length; k++) {
                            if (a[k] == tmp)
                                a[k] = a[i];
                        }
                    }
                } else {
                    if (a[i] == 0) a[i] = a[j];
                    else a[j] = a[i];
                }
            }
            return null;
        }
    }

}